//
//  ProblemOffer63.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 63. 股票的最大利润
 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

 示例 1:
     输入: [7,1,5,3,6,4]
     输出: 5
     解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
          注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 示例 2:
     输入: [7,6,4,3,1]
     输出: 0
     解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 限制：
    0 <= 数组长度 <= 10^5
 */
@objcMembers class ProblemOffer63: NSObject {
    func solution() {
        print(maxProfitClearAlloc([7,1,5,3,6,4]))
        print(maxProfitClearAlloc([7,6,4,3,1]))
    }
    
    /*
     只能购买一次：
     1: 创建一个数组 dp[len]
     2: dp[i]: 假如在i的时候卖出，能够获取的最大利润
     3: dp[i] = prices[i] - min(0~i-1)
     4: 求dp里面的 max
     */
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }
        
        var dp = Array(repeating: 0, count: prices.count)
        
        var minValue = prices[0]
        for i in 1..<prices.count {
            if prices[i] > minValue {
                dp[i] = prices[i] - minValue
            }
            minValue = min(minValue, prices[i])
        }
        return dp.max() ?? 0
    }
    
    /*
     优化：
     dp只是存储，最后就是求数组的最大值，那么用一个变量存储就行
     */
    func maxProfitClearAlloc(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }
        
        var minValue = prices[0]
        var maxValue = 0
        for i in 1..<prices.count {
            if prices[i] > minValue {
                maxValue = max(maxValue, prices[i] - minValue)
            }
            minValue = min(minValue, prices[i])
        }
        return maxValue
    }
}
